package 最大公约数_同余原理;

// 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
// 给定三个整数 n , a , b ，返回第 n 个神奇的数字。
// 因为答案可能很大，所以返回答案 对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/nth-magical-number/
public class Code02_NthMagicalNumber {

    public int nthMagicalNumber(int n, int a, int b) {
        // a, b 的最小公倍数，以便再一个范围内例如1~100内，
        // 统计有多少个符合条件的“神奇的数字”进行去重
        long lcm = lcm(a, b);
        long ans = 0;
        // l = 0
        // r = (long) n * Math.min(a, b)
        // l......r 这个范围内一定有满足条件的n个神奇的数字
        for(long l = 0, r = (long) n * Math.min(a, b), mid = 0; l <= r;){
            mid = (l + r) / 2;
            // l~mid 范围内 mid/a 能被a整除的数字的个数
            // l~mid 范围内 mid/b 能被b整除的数字的个数
            // l~mid 范围内 mid/lcm 既能能被a整除,又能能被b整除的数字的个数
            if(mid / a + mid / b - mid / lcm >= n){
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return (int) (ans % 1000000007);
    }

    // 求最大公约数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 求最小公倍数
    public static long lcm(long a, long b) {
        return (long)(a / gcd(a, b)) * b;
    }
}
